1. Field of the Invention
The present invention relates to layer 2 and layer 3 switching of data packets in a non-blocking network switch configured for switching data packets between subnetworks.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling network interface devices at each network node to access the network medium.
The Ethernet protocol IEEE 802.3 has evolved to specify a half-duplex media access mechanism and a full-duplex media access mechanism for transmission of data packets. The full-duplex media access mechanism provides a two-way, point-to-point communication link between two network elements, for example between a network node and a switched hub.
Switched local area networks are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. For example, commonly-assigned U.S. Pat. No. 5,953,335 discloses a network switch configured for switching layer 2 type Ethernet (IEEE 802.3) data packets between different network nodes; a received data packet may include a VLAN (virtual LAN) tagged frame according to IEEE 802.1q protocol that specifies another subnetwork (via a router) or a prescribed group of stations. Since the switching occurs at the layer 2 level, a router is typically necessary to transfer the data packet between subnetworks.
Efforts to enhance the switching performance of a network switch to include layer 3 (e.g., Internet protocol) processing may suffer serious drawbacks, as current layer 2 switches preferably are configured for operating in a non-blocking mode, where data packets can be output from the switch at the same rate that the data packets are received. Newer designs are needed to ensure that higher speed switches can provide both layer 2 switching and layer 3 switching capabilities for faster speed networks such as 100 Mbps or gigabit networks.
However, such design requirements risk loss of the non-blocking features of the network switch, as it becomes increasingly difficult for the switching fabric of a network switch to be able to perform layer 3 processing at the wire rates (i.e., the network data rate).
There is a need for an arrangement that enables a network switch to provide layer 2 switching and layer 3 switching capabilities for 100 Mbps and gigabit links without blocking of the data packets.
There is also a need for an arrangement that enables a network switch to provide layer 2 switching and layer 3 switching capabilities with minimal buffering within the network switch that may otherwise affect latency of switched data packets.
There is also a need for an arrangement that enables a network switch to be easily programmable to distinguish between different types of layer 3 data packets, wherein the network switch can interact with the host processor in loading min terms, used in evaluating layer 3 data packets, into specialized memories within a network switch port.
There is also a need for an arrangement to enable a network switch port to instantaneously evaluate an incoming data packet and determine a layer 3 or higher protocol, to provide the associated switch fabric with sufficient time to process the incoming data packet according to the detected protocol.
There is also a need for an arrangement that minimizes required memory space in a network switch port by optimizing the storage of min terms, used in evaluating layer 3 data packets, for evaluation of the most relevant data bytes of the layer 3 data packets.
These and other needs are attained by the present invention, where a network switch port includes a filter configured for evaluating an incoming data packet on an instantaneous basis. The filter performs simultaneous comparisons between the incoming data stream of the data packet and multiple templates configured for identifying respective protocols. Each template is composed of a plurality of min terms, where each min term specifies a prescribed comparison operation with a selected data byte of the incoming data packet. The filter includes a min term memory configured for storing the min term values in allocated memory blocks having respective sizes, controlled by a min term controller, based on the relevance of each min term to the evaluation of the incoming data packet. The mil term memory is configured for having a larger dedicated memory portion for min terms having more layer 3 information, and a smaller or equal size memory portion for min terms having less layer 3 information. The min term controller accesses the min terms based on the ordering of the data bytes, such that the min terms that are used to compare the first data byte are first accessed for comparison with the first data byte as the first data byte is received; the min terms used to compare the second data byte are then accessed for comparison with the second data byte as the second data byte is received. Hence, the filter simultaneously compares the min terms that correspond to the selected byte of the incoming data packet as the selected byte is received by the network switch port. The results of the comparisons between the min terms and the selected data bytes of the incoming data stream are evaluated by an equation core within the filter, which determines comparison results for the templates and outputs a tag to the switching core, providing the switching core with information on how to process the received data packet. Hence, the switching core has sufficient time to perform layer 2 or layer 3 switching of the received data packet in a non-blocking manner in a high-speed data network.
One aspect of the present invention provides a method of storing min terms to be used in evaluating an incoming data packet at a network switch port. The method includes receiving from a host controller a plurality of templates configured for simultaneous identification of respective data formats in the incoming data packet. Each template has at least one min term configured for comparing a corresponding prescribed value to a corresponding selected byte of the incoming data packet. The method also includes allocating memory block sizes based on relevance of respective incoming data bytes of the incoming data packet to evaluation of the incoming data packet, and storing the min terms in a min term memory within the network switch port. The storing of min terms includes storing a first group of the min terms configured for simultaneous comparison with a corresponding first of the incoming data bytes in a first memory block within the min term memory, and storing a second group of the min terms configured for simultaneous comparison with a corresponding second of the incoming data bytes having a respective relevance less than the first of the data bytes in a second memory block within the min term memory, the second memory block having a size less than the first memory block. The storage of templates configured for identifying respective data formats enables the network switch port to be easily programmable to identify user-defined data formats. Moreover, the storage of the min terms in memory blocks having allocated sizes based on the relevance to evaluation of the incoming data packet enables the memory to be optimized to store the most relevant min terms in the largest amount of memory space, while limiting relatively nonrelevant min terms to a relatively small portion of the min term memory.
Another aspect of the present invention provides a method of evaluating an incoming data packet at a network switch port. The method includes receiving from a host controller a plurality of templates configured for simultaneous identification of respective data formats in the incoming data packet, each template configured for identifying a prescribed format within the incoming data packet and having at least one min term configured for comparing a corresponding prescribed value to a corresponding selected byte of the incoming data packet. The method also includes storing each of the min terms into a min term memory within the network switch port into a corresponding one of a plurality of memory blocks, the one memory block having a memory block size based on a corresponding relevance of the corresponding selected byte to evaluation of the incoming data packet. The bytes of the incoming data packet are simultaneously compared with a plurality of the templates by fetching, for each byte, a group of the stored min terms from the corresponding memory block and simultaneously comparing the corresponding byte with the corresponding fetched group of the stored min terms; and generating a comparison result based on min term results from the comparisons of the bytes relative to the plurality of templates. The storing of the min terms based on the relevance effectively provides a compression of data within the min term memory, optimizing the memory to store the min terms for the most relevant data bytes, while min terms for less relevant data bytes occupy a lesser portion of the min term memory. Finally, the simultaneous comparison of the bytes with the plurality of templates by fetching a group of the stored min terms ensures that the min terms are sequentially processed based on the order in which the min terms are stored. Hence, multiple templates may be processed simultaneously and in real time, enabling an incoming data packet to be evaluated at the network switch port in real time, minimizing latency in the network switch port.
Still another aspect of the present invention provides a network switch port filter configured for evaluating an incoming data packet. The network switch port filter includes a min term memory configured for storing min term values and having a plurality of memory blocks. Each min term value is stored in a selected memory block, having a corresponding size, based on at least one of a location of a corresponding selected byte of the incoming data packet for comparison and a relevance of the corresponding selected byte to evaluation of the incoming data packet. The network switch port filter also includes a min term controller configured for storing the min term values into the min term memory. The min term controller stores each min term in one of the memory blocks based on the corresponding relevance to the evaluation of the incoming data packet. The network switch port filter also includes a min term generator, and an equation core. The min term generator is configured for simultaneously comparing a received byte of the incoming data packet with the min terms stored in the memory block that corresponds to the received byte, and generating respective min term comparison results. The equation core is configured for generating a frame tag identifying the incoming data packet based on the min term comparison results relative to the template. The min term controller stores each of the min terms in a selected portion of the min term memory based on the corresponding relevance to the evaluation of the incoming data packet, enabling storage of the min terms to be optimized for simultaneous comparisons of the most relevant data bytes of the incoming data packet as they are received. Hence, the min term generator can simultaneously compare a given received byte of the incoming data packet with all the relevant min terms, enabling real-time evaluation of the incoming data packet.
Additional advantages and novel features of the invention will be set forth in part in the description which follows and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The advantages of the present invention may be realized and attained by means of instrumentalities and combinations particularly pointed in the appended claims.